/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package cz.dusa.switco;

import java.util.ArrayList;
import java.util.List;

/**
 * Equality tree is a structure encapsulating the equality tree from the article.
 * @author vdusa
 */
public class EqualityTree {

    private TasksHolder tasksHolder = new TasksHolder();
    private List<Precedence> treePrecedences;
    private double start = 0.0;
    private long id = 0;

    public EqualityTree(List<Task> tasks, List<Precedence> treePrecedences) {
        this.tasksHolder = new TasksHolder(tasks);

        if (treePrecedences == null) {
            this.treePrecedences = new ArrayList<Precedence>();
        } else {
            this.treePrecedences = treePrecedences;
        }
    }

    /**
     * Merges the given tree to the current tree.
     * 
     * @param precedence is the precedence connecting two trees.
     * The precedence must contain current tree either as a predecessor or as a successor.
     */
    public void merge(Precedence precedence) {
        EqualityTree predecessorTree = precedence.getPredecessor().getEqualityTree();
        EqualityTree successorTree = precedence.getSuccessor().getEqualityTree();
        Task predecessor = precedence.getPredecessor();
        Task successor = precedence.getSuccessor();

        assert ((predecessorTree.equals(this) && !successorTree.equals(this))
                || (!predecessorTree.equals(this) && successorTree.equals(this))) : "Given precedence must connect this tree with another one.";
        assert (GlobalSettings.getInstance().roundToPrecisionLimit(predecessor.getStart() + precedence.getValue() - successor.getStart())==0) : "You are merging trees, that are not touching each other in at the precedence. It would be no 'equality tree' then.";

        double treeShiftCorrection = successorTree.getStart() - predecessorTree.getStart();
        if (treeShiftCorrection > 0.0) {
            /* successorTree starts later than predecessorTree, thus the treeShift of the
             * successorTree tasks must be updated according to the new position in the new
             * merged tree.
             */
            for (Task task : successorTree.getTasksHolder().getTasks()) {
                task.setTreeShift(task.getTreeShift() + treeShiftCorrection);
            }
        } else {
            /* successorTree start earlier than predecessorTree, thus the treeShift of the 
             * predecessorTree tasks must be updated according to the new position in the new 
             * merged tree.
             */
            for (Task task : predecessorTree.getTasksHolder().getTasks()) {
                task.setTreeShift(task.getTreeShift() - treeShiftCorrection);
            }
        }

        EqualityTree otherTree = predecessorTree.equals(this) ? successorTree : predecessorTree;

        //move tasks to the current tree
        for (Task task : otherTree.getTasksHolder().getTasks()) {
            task.setEqualityTree(this);
            tasksHolder.add(task);
        }

        //move precedences to the current tree
        treePrecedences.addAll(otherTree.getTreePrecedences());
        treePrecedences.add(precedence);

        //set start to the minimum
        this.setStart(successorTree.getStart()<predecessorTree.getStart()?successorTree.getStart():predecessorTree.getStart());

        otherTree.die();
    }

    /**
     * Splits the current equality tree into two parts. Current equality tree
     * will become the left part. The right part is returned.
     *
     * @param precedence Precedence where the current equality tree should be splitted
     * @return right part of the tree.
     */
    public EqualityTree split(Precedence precedence) {
        List<Task> successorTasks = new ArrayList<Task>();
        List<Precedence> successorPrecedences = new ArrayList<Precedence>();
        double successorTreeStart = Double.MAX_VALUE;
        double predecessorTreeStart = Double.MAX_VALUE;

        assert (treePrecedences.contains(precedence)) : "Task::split() -> Given precedence is not precedence of the EqualityTree.";

        List<Task> notCheckedSuccessorTasks = new ArrayList<Task>();
        notCheckedSuccessorTasks.add(precedence.getSuccessor());
        getTreePrecedences().remove(precedence);
        
        do {
            Task successorTask = notCheckedSuccessorTasks.remove(0);
            if (successorTreeStart > successorTask.getStart()) {
                successorTreeStart = successorTask.getStart();
            }

            if (getTasksHolder().getTasks().contains(successorTask)) {
                successorTasks.add(successorTask);
                getTasksHolder().remove(successorTask);
            }
            
            for(Precedence successorPrecedence: successorTask.getSuccessors()){
                if (getTreePrecedences().contains(successorPrecedence)) {
                    successorPrecedences.add(successorPrecedence);
                    notCheckedSuccessorTasks.add(successorPrecedence.getSuccessor());
                    getTreePrecedences().remove(successorPrecedence);
                }
            }
            
            for(Precedence predecessorPrecedence: successorTask.getPredecessors()){
                /* It can't go back through already explored path, because as soon any
                 * precedence is checked, it is immediately removed from treePrecedences.
                 */
                if (getTreePrecedences().contains(predecessorPrecedence)) {
                    successorPrecedences.add(predecessorPrecedence);
                    notCheckedSuccessorTasks.add(predecessorPrecedence.getPredecessor());
                    getTreePrecedences().remove(predecessorPrecedence);
                }            
            }
            
        } while (notCheckedSuccessorTasks.size() > 0);        

        if (successorTreeStart == getStart()) {
            for (Task predecessor : getTasksHolder().getTasks()) {
                if (predecessorTreeStart > predecessor.getStart()) {
                    predecessorTreeStart = predecessor.getStart();
                }
            }
        } else {
            predecessorTreeStart = getStart();
        }

        EqualityTree successorTree = new EqualityTree(successorTasks, successorPrecedences);
        for(Task t: successorTree.getTasksHolder().getTasks()){
            t.setEqualityTree(successorTree);
        }
        Forest.getInstance().plantTree(successorTree);
        successorTree.setStart(successorTreeStart);
        setStart(predecessorTreeStart);

        double treeShiftCorrection = successorTreeStart - predecessorTreeStart;
        if (treeShiftCorrection > 0.0) {
            /* successorTree starts later than predecessorTree, thus the treeShift of the
             * successorTree tasks must be updated according to the new position in the new
             * stand-alone tree.
             */
            for (Task task : successorTree.getTasksHolder().getTasks()) {                
                task.setTreeShift(task.getTreeShift() - treeShiftCorrection);
            }
        } else {
            /* successorTree start earlier than predecessorTree, thus the treeShift of the 
             * predecessorTree tasks must be updated according to the new position in the new 
             * stand-alone tree.
             */
            for (Task task : getTasksHolder().getTasks()) {
                task.setTreeShift(task.getTreeShift() + treeShiftCorrection);
            }
        }
        
        return successorTree;
    }

    /**    
     * @param direction 
     * @param pivot 
     * @return {@link Event} where the active equality tree will no longer be active equality
     * because of hitting another active equality tree tree or it must be splitted or it falls into the optimum
     * according to the cost function. If there is no event caused by any precedence, null will be returned.
     */
    public Event getNearestEvent(MovingDirection direction, Task pivot) {
        //Event caused by splitting current tree
        Event splitEvent = getNearestSplitEvent(direction, pivot);

        //Event caused by merging with other trees
        Event mergeEvent = getNearestMergeEvent(direction);
        
        Double time;
        Event event = null;

        switch (direction) {
            case BACKWARDS:
                time = GlobalSettings.getInstance().getMinT()-1;
                if (mergeEvent != null && mergeEvent.getTime() >= time && mergeEvent.getTime() <= getStart()) {
                    time = mergeEvent.getTime();
                    event = mergeEvent;
                }
                if (splitEvent != null && splitEvent.getTime() >= time && splitEvent.getTime() <= getStart()) {
                    time = splitEvent.getTime();
                    event = splitEvent;
                }
                break;
            case FORWARD:
                time = GlobalSettings.getInstance().getMaxT()+1;
                if (mergeEvent != null && mergeEvent.getTime() <= time && getStart() <= mergeEvent.getTime()) {
                    time = mergeEvent.getTime();
                    event = mergeEvent;
                }
                if (splitEvent != null && splitEvent.getTime() <= time && getStart() <= splitEvent.getTime()) {
                    time = splitEvent.getTime();
                    event = splitEvent;
                }
                break;
            default:
                throw new RuntimeException("Unknown MovingDirection " + direction.toString());
        }

        return event;
    }

    /**
     * @param precedence splitting the equality tree into two parts
     * @return all predecessors of the given precedence in the current tree. The 
     * first predecessor defining the precedence is also included.
     */
    public TasksHolder getLeftTasks(Precedence precedence) {
        List<Precedence> treePrecedencesBuffer = new ArrayList<Precedence>();        
        treePrecedencesBuffer.addAll(getTreePrecedences());
        treePrecedencesBuffer.remove(precedence);

        return getComponentContainingTask(treePrecedencesBuffer, precedence.getPredecessor());

    }

    /**
     * @param precedence splitting the equality tree into two parts
     * @return all successors of the given precedence in the current tree. The 
     * first successor defining the precedence is also included.
     */
    public TasksHolder getRightTasks(Precedence precedence) {                
        List<Precedence> treePrecedencesBuffer = new ArrayList<Precedence>();        
        treePrecedencesBuffer.addAll(getTreePrecedences());
        treePrecedencesBuffer.remove(precedence);

        return getComponentContainingTask(treePrecedencesBuffer, precedence.getSuccessor());
    }
    
    /**
     * @param precedences making the components of the current equality tree
     * @param task component containing this task will be returned
     * @return tasks from the current equality tree connected by given precedences
     * and containing given task
     */
    private TasksHolder getComponentContainingTask(List<Precedence> precedences, Task task){        
        List<Task> taskBuffer = new ArrayList<Task>();
        TasksHolder tasks = new TasksHolder();
        
        taskBuffer.add(task);
        
        while (!taskBuffer.isEmpty()) {
            Task t = taskBuffer.remove(0);
            tasks.add(t);
            for (Precedence p : t.getSuccessors()) {
                //@performance contains() tady asi nebude nejefektivnější. Lepší bude když Precedence bude mít link na EqualityTree pokud v něm je.
                if (precedences.contains(p)) {
                    if(!taskBuffer.contains(p.getSuccessor())){ //against infinite loop
                        taskBuffer.add(p.getSuccessor());
                    }
                    precedences.remove(p);
                }
            }

            for (Precedence p : t.getPredecessors()) {
                //@performance contains() tady asi nebude nejefektivnější. Lepší bude když Precedence bude mít link na EqualityTree pokud v něm je.
                if (precedences.contains(p)) {
                    if(!taskBuffer.contains(p.getPredecessor())){ //against infinite loop
                        taskBuffer.add(p.getPredecessor());
                    }
                    precedences.remove(p);
                }
            }            
        }
    
        return tasks;
    }

    /**
     * Returns start position of the current tree, where it must be splitted into two parts
     * according to the definition of ACTIVE equality tree. Behind this time point is the current tree 
     * no more active.
     * @param direction in which we are looking for the split event
     * @return {@link Event}
     */
    public Event getNearestSplitEvent(MovingDirection direction, Task pivotTask) {
        NearestEventHolder nearestEventHolder = new NearestEventHolder(direction);
        
        for(Precedence p: pivotTask.getSuccessorsInEqualityTree(this)){
            findNearestSplitEvent(p, false, nearestEventHolder, direction);
        }

        for(Precedence p: pivotTask.getPredecessorsInEqualityTree(this)){
            findNearestSplitEvent(p, true, nearestEventHolder, direction);
        }
        
        return nearestEventHolder.getEvent();
    }
    
    private ConvexCostFunctionSum findNearestSplitEvent(Precedence precedence, boolean incomingOpposite, NearestEventHolder nearestEventHolder, MovingDirection direction) {
        Task task;
        ConvexCostFunctionSum sum = new ConvexCostFunctionSum();

        if(incomingOpposite){
            task = precedence.getPredecessor();
        } else{
            task = precedence.getSuccessor();
        }

        for(Precedence p: task.getSuccessorsInEqualityTree(this)){
            if(!p.equals(precedence)){
                sum.addCostFunction(findNearestSplitEvent(p, false, nearestEventHolder, direction));
            }
        }
        
        for(Precedence p: task.getPredecessorsInEqualityTree(this)){
            if(!p.equals(precedence)){
                sum.addCostFunction(findNearestSplitEvent(p, true, nearestEventHolder, direction));
            }
        }
        
        sum.addCostFunction(task.getCostFunction());

        if((direction==MovingDirection.BACKWARDS && !incomingOpposite) || (direction==MovingDirection.FORWARD && incomingOpposite)){ //just in this case the tree can be split
            Double[] splitTimeInterval = sum.getArgMin();
            Double splitTime;
            switch (direction) {
                case BACKWARDS:
                    splitTime = splitTimeInterval[1];
                    break;
                case FORWARD:
                    splitTime = splitTimeInterval[0];
                    break;
                default:
                    throw new RuntimeException("Unknown MovingDirection " + direction.toString());                                
            }

            nearestEventHolder.compare(new Event(splitTime, precedence, EventType.SPLIT));
        }
        
        return sum;
    }

    /**
     * Returns start position of the current tree, where it must be merged with another tree because of 
     * some precedence(either the tree has bumped into another one or some precedence with maximal distance>0
     * pulls another tree.
     * @param direction in which we are looking for the merge event
     * @return {@link Event}
     */
    public Event getNearestMergeEvent(MovingDirection direction) {
        double touchTime;
        double newTouchTime;
        Precedence bumperPrecedence = null;
        NearestEventHolder nearestEventHolder = new NearestEventHolder(direction);

        switch (direction) {
            case BACKWARDS:
                touchTime = -1.0;
                for (Task successor : getTasksHolder().getTasks()) {
                    for (Precedence p : successor.getPredecessors()) {
                        Task predecessor = p.getPredecessor();
                        if (predecessor.getEqualityTree() != this) {
                            newTouchTime = predecessor.getStart() + p.getValue() - successor.getTreeShift();
                            nearestEventHolder.compare(new Event(newTouchTime, p, EventType.MERGE));
                        }
                    }
                }
                
                assert touchTime <= getStart() : "Nearest left merge-event found right from start of the tree. Something is wrong.";                
                break;
            case FORWARD:
                touchTime = Double.MAX_VALUE;
                for (Task predecessor : getTasksHolder().getTasks()) {
                    for (Precedence p : predecessor.getSuccessors()) {
                        Task successor = p.getSuccessor();
                        if (successor.getEqualityTree() != this) {
                            newTouchTime = successor.getStart() - p.getValue() - predecessor.getTreeShift();                            
                            nearestEventHolder.compare(new Event(newTouchTime, p, EventType.MERGE));
                        }
                    }
                }
                               
                assert touchTime >= getStart() : "Nearest right merge-event found left from the start of the tree. Something is wrong.";                
                break;
            default:
                throw new RuntimeException("Unknown MovingDirection " + direction.toString());
        }

        return nearestEventHolder.getEvent();        
    }

//    /**
//     * Returns a point where the current tree would like to be (optimal start position
//     * according to the convex cost functions of activities building the tree)
//     * @param direction in which we are looking for the fix event
//     * @return {@link Event}
//     */
//    public Event getNearestFixEvent(MovingDirection direction) {
//        Double[] optimalTimeWindow = getTasksHolder().getOptimalStartTimeWindow();
//        return new Event(optimalTimeWindow[0], optimalTimeWindow[1], null, EventType.FIX);
//    }

    /**
     * @return true if the current equality tree is active equality tree
     */
    public boolean isActive() {
        for (Precedence precedence : getTreePrecedences()) {
            TasksHolder predecessingTasks = getLeftTasks(precedence);
            TasksHolder successingTasks = getRightTasks(precedence);

            if ((predecessingTasks.isStrictlyEarly() && successingTasks.isLate())
                    || (predecessingTasks.isEarly() && successingTasks.isStrictlyLate())) {
                //precedence is active
            } else {
                //precedence is not active
                return false;
            }
        }

        //all precedences are active
        return true;
    }

    /**
     * Never change tasks from outside.
     * @return the tasks
     */
    public TasksHolder getTasksHolder() {
        return tasksHolder;
    }

    /**
     * @return the treePrecedences
     */
    public List<Precedence> getTreePrecedences() {
        return treePrecedences;
    }

    /**
     * @param treePrecedences the treePrecedences to set
     */
    private void setTreePrecedences(List<Precedence> treePrecedences) {
        this.treePrecedences = treePrecedences;
    }

    /**
     * @return the start of the equality tree
     */
    public double getStart() {
        return start;
    }

    /**
     * @param start the start of the equality tree to set
     */
    public void setStart(double start) {
        this.start = start;
    }

    /**
     * @return true if the tree is strictly early
     */
    public boolean isStrictlyEarly() {
        return getTasksHolder().isStrictlyEarly();
    }

    /**
     * @return true if the tree is early
     */
    public boolean isEarly() {
        return getTasksHolder().isEarly();
    }

    /**
     * @return true if the tree is on time (i.e. it is early and late together)
     */
    public boolean isOnTime() {
        return isEarly() && isLate();
    }

    /**
     * @return true if the tree is late
     */
    public boolean isLate() {
        return getTasksHolder().isLate();
    }

    /**
     * @return true if the tree is strictly late
     */
    public boolean isStrictlyLate() {
        return getTasksHolder().isStrictlyLate();
    }

    /**
     * Clears the current tree and removes itself from the {@link Forest}.
     */
    private void die() {
        tasksHolder.clear();
        treePrecedences.clear();
        tasksHolder.setConvexCostFunctionSum(null);
        start = 0.0;
        Forest.getInstance().chopTree(this);
    }

    /**
     * @return the id
     */
    public long getId() {
        return id;
    }

    /**
     * @param id the id to set
     */
    public void setId(long id) {
        this.id = id;
    }

    @Override
    public String toString(){
        String output = "";
        for(Task t: getTasksHolder().getTasks()){
            output += ((output.equals("")?"":",") + t);
        }
        return "{" + output + "}";
    }

    /**
     * Splits the current tree at each precedence that is not active. Call this function only if 
     * the tree is on time!
     */
    public void splitAtInactivePrecedences() {
        assert isOnTime() : "Tree can be split at inactive precedences only if it is on time!";
        
        List<Precedence> precedences = new ArrayList<Precedence>(getTreePrecedences());
        for (Precedence precedence : precedences) {
            TasksHolder predecessingTasks = getLeftTasks(precedence);
            TasksHolder successingTasks = getRightTasks(precedence);

            if ((predecessingTasks.isStrictlyEarly() && successingTasks.isLate())
                    || (predecessingTasks.isEarly() && successingTasks.isStrictlyLate())) {
                //precedence is active
            } else {
                EqualityTree t = precedence.getPredecessor().getEqualityTree();
                t.split(precedence);
            }
        }
    }

    public boolean existsDirectedPath(Task source, Task target){
        List<Precedence> successors = new ArrayList<Precedence>();        
        //todo: place to be optimized - complexity is too high here 
        
        if(source.equals(target)){
            return true;
        }

        successors.addAll(source.getSuccessors());
        while(successors.size()>0){
            Precedence precedence=successors.remove(0);
            if(treePrecedences.contains(precedence)){
                if(precedence.getSuccessor().equals(target)){
                    return true;
                }
                successors.addAll(precedence.getSuccessor().getSuccessors());
            }
        } 
        
        return false;
    }
}
